package _03_recursion;

import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/1 - 13:52
 * 多路递归 打印斐波那契数列
 *  n=0/1特殊处理，否则正整数n = (n-1) + (n-2)
 *  0    1   2   3   4   5   6   7   8   9   10  11  12     13      14
 *  0    1   1   2   3   5   8   13  21  34  55  89  144    233     377
 *
 *
 *  递归方法需执行的次数 = 2*f(n+1) - 1
 */
public class FibonacciTest {
    @Test
    public void test() {
        for (int i = 0; i <= 20; i++) {
            System.out.print(foo(i) + ",");
        }
    }

    /**
     * 要求n >= 0
     * @param n
     * @return
     */
    private int foo(int n) {
        if(n == 0 || n == 1) {
            return n;
        }
        return foo(n - 1) + foo(n - 2);
    }
}
